1. Field of the Invention
This invention relates to a method of logic cell placement for an automatic layout system with which logic cells are arranged on a semiconductor circuit, and more particularly to a method for generating clusters formed by interconnecting logic cells.
2. Description of the Prior Art
Because of the rapid progress of fine fabrication technology for Very Large Scale Integration (VLSI) circuits in recent years, VLSI circuits can be fabricated using such fine fabrication technology.
Many automatic layout systems have been developed in efforts to reduce chip area of VLSI and the amount of computer time for arranging logic cells on a semiconductor chip. A three-stage arrangement method is the most commonly used automatic layout system. The three-stage arrangement method is divided into a pretreatment process, an initial arranging process, and an arrangement improvement process.
In the pretreatment process, a cluster is formed with a group of logic cells which have strong connection strengths to each other, but weak external connections to other groups. In the initial arranging process, the clusters are arranged on the semiconductor chip temporarily. In the arrangement improvement process, the position of the cluster arranged by the initial arranging process is changed for improved arrangement.
Where the three-stage arrangement method is used as the automatic placement method, the better the result of the earlier process is, the more the arrangement of the logic cells finally obtained is effected.
Therefore it is important to get very good results in the earlier process so as to optimize chip area.
A clustering method for grouping logic cells is usually used in the pretreatment process. There are two reasons for this.
The first reason is that the clustering method can reduce the total processing time or the amount of computer time for arranging the logic cells on the chip. Namely, the cluster is used as one logic cell, so that the number of objects for calculation of arranging in the method becomes smaller than where the clustering method is not used.
The second reason is that logic cells having a strong connection strength or a strong relation to one another are collected into a cluster by the clustering method so that wiring lengths between the logic cells can be reduced.
In conventional clustering methods, two calculation methods are generally well known.
In the first calculation method for clustering logic cells, cells having a strong connection strength are grouped so as to generate a cluster based on the strong connections of signals to be transferred among the logic cells. In such a case, the connection strength between the clusters is given by the following equation: ##EQU1## where: Cab: the number of wirings connected between clusters A and B;
Ca: the number of wirings connected between the cluster A and clusters other than the cluster A in the cluster A; and PA1 Cb: the number of wirings connected between the cluster B the clusters other than the cluster B in the cluster B.
A well known reference about the calculation method for clustering is Donald M. Schuler and Ernest G. Ulrich, "CLUSTERING AND LINEAR PLACEMENT", Proceedings of 9th Annual Design Automation Workshop, pp.50-56, 1972.
In one step for generating a cluster in this method, an upper limit of an area of the cluster is used, so as to simplify handling of the clusters. Moreover an upper limit of the number of logic cells per cluster is also used for each wiring between the clusters as restrictions in the initial arrangement process.
In a second method logic cells having a similar function are grouped by utilizing a hierarchy structure of a net list.
However, detailed information such as the number of terminals in each cluster, the number of wirings which can be wired on a logic cell, and the size of a logic cell in the cluster are not considered in the conventional clustering methods described above. Accordingly, the degree of possibility for wiring in each cluster is different to each other.
A cluster having many terminals is generated by the unbalance of the number of terminals among clusters, so that an area with crowded wirings in the cluster is supplied.
A cluster having a small number of wirings which can be wired on a logic cell is generated by the unbalance of the number of wirings which can be wired on each cluster.
Accordingly, when a wiring is required in an area around the cluster, it is necessary that a cell only used for wiring, or a field through cell, be inserted next to the cluster or the wiring to be wired around the cluster should be wired around it.
These can become a main cause for increasing the length of a cell block or a width of a channel.
A cluster having many small logic cells is generated by an unbalance or size of logic cell area among clusters, so that a difference in the number of terminals or wirings which can be wired on a logic cell occurs among the clusters.
FIG. 1 shows a schematic diagram for explanation of a cluster having many small logic cells such as a NAND circuit, a NOR circuit, or IV (inverter) circuit (where only one wiring can not wired) centered in an area. Namely, only one wiring can not be wired on the small logic cell. While many wirings are wired on a large logic cell having almost the same number of terminals as the small logic cell.
In the same diagram, reference number 1 denotes a logic cell as the small logic cell having no wiring thereon, reference number 2 designates a logic cell having two wiring thereon as the large logic cell, and reference number 3 designates wiring on the logic cell 2.
As clearly shown in FIG. 1, where there are wirings around the small logic cell 1, the wirings must be wired round it or on the field through cell as a dummy logic cell is incorporated next the small logic cell 1 so that the width of the block relating to the small logic cell or the number of tracks should be increased for the wirings.